package com.xinwei.leetcode.数组;

import java.nio.file.StandardWatchEventKinds;

// https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
public class _33_搜索旋转排序数组 {
    public static int search(int[] nums, int target) {
        if (nums.length == 1) {
            return (nums[0] == target) ? 0 : -1;
        }
        // 先把他恢复成未旋转的排序数组
        int len = nums.length;
        int[] newNums = new int[2 * len];
        int j = 0;
        int right = 0;
        for (int i = 0; i < newNums.length; i++) {
            if (i >= len) {
                j = i - len;
            }else {
                j = i;
            }
            newNums[i] = nums[j];
            if (i > 0 && newNums[i] < newNums[i - 1]) {
                right = i;
            }
        }
        int left = right - len;
        int result = search(newNums, left, right, target);
        return (result >= len) ? result - len : result;
    }

    // 二分搜索
    private static int search(int[] nums, int left, int right, int target) {
        int mid = (left + right) >> 1;
        if (target == nums[mid]) return mid;
        if (right - left <= 1) return -1;
        if (target > nums[mid]) {
            return search(nums, mid, right, target);
        }else {
            return search(nums, left, mid, target);
        }
    }
}
